package com.leetcode.algorithm.y22.m07.w3;

import java.util.Arrays;

/**
 * 910. 最小差值 II
 * 
 * https://leetcode.cn/problems/smallest-range-ii/
 * 
 * @author jie.deng
 *
 */
class Question0910Solution01 {

	public int smallestRangeII(int[] nums, int k) {
		int len = nums.length;
		if (len == 1) {
			return 0;
		}

		Arrays.sort(nums);
		// 全部朝一个方向加减k的情况
		int ans = nums[len - 1] - nums[0];
		if (k == 0) {
			return ans;
		}
		int first = nums[0] + k;
		int last = nums[len - 1] - k;

		for (int i = 1; i <= nums.length - 1; i++) {
			// 从第i个元素开始减
			int min = Math.min(first, nums[i] - k);
			int max = Math.max(last, nums[i - 1] + k);
			ans = Math.min(ans, max - min);
		}

		return ans;
	}

}